#define _CRT_SECURE_NO_WARNINGS
#include <iostream>

using namespace std;

struct ListNode {
	int val;
	ListNode* next;
	ListNode() : val(0), next(nullptr) {}
	ListNode(int x) : val(x), next(nullptr) {}
	ListNode(int x, ListNode* next) : val(x), next(next) {}
};
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if (head == nullptr || head->next == nullptr)
        {
            return head;
        }

        ListNode* newHead = swapPairs(head->next->next);
        ListNode* next = head->next;
        head->next = newHead;
        next->next = head;

        return next;
    }
};
int main()
{
    ListNode* head = new ListNode;
    head->val = 1;
    ListNode* l2 = new ListNode;
    l2->val = 2;
    ListNode* l3 = new ListNode;
    l3->val = 3;
    ListNode* l4 = new ListNode;
    l4->val = 4;
    head->next = l2;
    l2->next = l3;
    l3->next = l4;
    l4->next = nullptr;
    Solution s;
    s.swapPairs(head);
	return 0;
}